package cn.conchit.apccontroldemo.graph.canvas;


import cn.conchit.apccontroldemo.graph.exception.DirectGraphException;
import cn.conchit.apccontroldemo.graph.exception.GraphNodeLinkException;
import cn.conchit.apccontroldemo.graph.exception.NoSuchGraphEdgeException;
import cn.conchit.apccontroldemo.graph.exception.NoSuchGraphNodeException;
import lombok.Data;

import java.util.*;


/**
 * @author hetao
 * @version 1.0
 * @description: TODO
 * @date 2023/2/12 15:34
 */

@Data
public class CanvasGraph<V extends CmptVertex, E> implements IDirectGraph<V, E>, Cloneable {

    private List<CmptNode<V>> nodeList;
    private int edgeNum;

    /**
     * @description: 有向图中维护节点索引。每当节点添加到有向图之后，索引自增
     */
    private int nodeIndex;

    public CanvasGraph() {
        this.nodeList = new ArrayList<CmptNode<V>>();
        nodeIndex = 0;
    }

    public int getNodeIndex(V vertexData) throws NoSuchGraphNodeException {
        ListIterator<CmptNode<V>> iterator =  nodeList.listIterator();
        while (iterator.hasNext()) {
            CmptNode<V> CmptNode = iterator.next();
            if(CmptNode.getVertex().equals(vertexData)) {
                return CmptNode.getIndex();
            }
        }
        throw new NoSuchGraphNodeException(vertexData.toString());
    }

    public CmptNode<V> getNode(V vertexData) throws NoSuchGraphNodeException {
        ListIterator<CmptNode<V>> iterator =  nodeList.listIterator();
        while (iterator.hasNext()) {
            CmptNode<V> cmptNode = iterator.next();
            if(cmptNode.getVertex().equals(vertexData)) {
                return cmptNode;
            }
        }
        throw new NoSuchGraphNodeException(vertexData.toString());
    }

    public CmptNode<V> getNode(int index) throws NoSuchGraphNodeException {
        ListIterator<CmptNode<V>> iterator =  nodeList.listIterator();
        while (iterator.hasNext()) {
            CmptNode<V> cmptNode = iterator.next();
            if(cmptNode.getIndex()==index) {
                return cmptNode;
            }
        }
        throw new NoSuchGraphNodeException("index="+index);
    }

    @Override
    public V getVertex(int index) throws NoSuchGraphNodeException {
        CmptNode<V> node = getNode(index);
        return node.getVertex();
    }

    @Override
    public void addVertex(V v) {
//        CmptNode<V> CmptNode = new CmptNode(v, ++nodeIndex);
        CmptNode<V> cmptNode = CmptFactory.createNode(v);
        cmptNode.setIndex(++nodeIndex);
        nodeList.add(cmptNode);
    }

    @Override
    public boolean removeVertex(V v) throws DirectGraphException {
        CmptNode<V> removeNode = getNode(v);
        for(Edge pEdgeIn = removeNode.getFirstIn(); pEdgeIn != null; pEdgeIn = pEdgeIn.getHeadLink()) {
            removeEdge(pEdgeIn);
        }

        for(Edge pEdgeOut = removeNode.getFirstOut(); pEdgeOut != null; pEdgeOut = pEdgeOut.getTailLink()) {
            removeEdge(pEdgeOut);
        }
        nodeList.remove(removeNode);
        return true;
    }

    @Override
    public void addEdge(Edge<E> edge) throws DirectGraphException {
        if(edge.getTailIndex() == edge.getHeadIndex()) {
            throw new GraphNodeLinkException(edge.toString());
        }
        CmptNode tailNode = getNode(edge.getTailIndex());
        CmptNode headNode = getNode(edge.getHeadIndex());

        edge.setTailLink(tailNode.getFirstOut());
        tailNode.setFirstOut(edge);

        edge.setHeadLink(headNode.getFirstIn());
        headNode.setFirstIn(edge);
        edgeNum++;

    }

    @Override
    public boolean removeEdge(Edge<E> edge) throws DirectGraphException  {
        if(edge.getTailIndex() == edge.getHeadIndex()) {
            throw new GraphNodeLinkException("edge from " + edge.getTailIndex() + " to " + edge.getHeadIndex());
        }
        CmptNode tailNode = getNode(edge.getTailIndex());
        CmptNode headNode = getNode(edge.getHeadIndex());

        Edge<E> p = tailNode.getFirstOut();
        if(edge.equals(p)) {
            tailNode.setFirstOut(p.getTailLink());
        } else {
            while(p != null) {
                Edge<E> q = p.getTailLink();
                if(edge.equals(q)) {
                    p.setTailLink(q.getTailLink());
                }
                p = p.getTailLink();
            }
        }

        p = headNode.getFirstIn();
        if (edge.equals(p)) {
            headNode.setFirstIn(p.getHeadLink());
        } else {
            while(p != null) {
                Edge<E> q = p.getHeadLink();
                if(edge.equals(q)) {
                    p.setHeadLink(q.getHeadLink());
                }
                p = p.getHeadLink();
            }
        }
        edgeNum--;

        return true;
    }

    @Override
    public boolean removeEdge(int tailIndex, int headIndex) throws DirectGraphException {
        return removeEdge(new Edge<>(tailIndex, headIndex, null));
    }

    @Override
    public Edge<E> getEdge(int tailIndex, int headIndex) throws DirectGraphException{
        if(tailIndex == headIndex) {
            throw new GraphNodeLinkException("tailIndex = headIndex error");
        }
        CmptNode<V> node = getNode(tailIndex);
        for(Edge<E> edge = node.getFirstOut(); edge != null; edge = edge.getTailLink()) {
            if(edge.getHeadIndex() == headIndex) {
                return edge;
            }
        }
        throw new NoSuchGraphEdgeException("edge from " + tailIndex + " to " + headIndex);
    }

    @Override
    public List<V> bfs(V root) {
        return null;
    }

    @Override
    public List<V> dfs(V root) {
        return null;
    }


    public List<HashSet<CmptNode>> sequence() throws CloneNotSupportedException, DirectGraphException {
        List<HashSet<CmptNode>> seqList = new ArrayList<HashSet<CmptNode>>();
        CanvasGraph<V, E> graph = (CanvasGraph<V, E>) this.clone();
        while(graph.nodeList.size() != 0) {
            HashSet<CmptNode> set = new HashSet<>();
            for(int i = 0; i < nodeList.size(); i++) {
                CmptNode node = nodeList.get(i);
                if(node.getFirstIn() == null) {
                    set.add(node);
                }
            }
            Iterator<CmptNode> it = set.iterator();
            while(it.hasNext()) {
                graph.removeVertex((V) it.next().getVertex());
            }
            seqList.add(set);
        }
        return  seqList;
    }

}
